package one.three.eleven;

import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class EvaluatePostfix {

	static class Stack<Item> implements Iterable<Item> {

		private Node<Item> first;
		private int n;

		public Stack() {
			first = null;
			n = 0;
		}

		public boolean isEmpty() {
			return first == null;
		}

		public int size() {
			return n;
		}

		public void push(Item item) {
			Node oldfirst = first;
			first = new Node();
			first.item = item;
			first.next = oldfirst;
			n++;
		}

		public Item pop() {
			if (isEmpty()) {
				throw new NoSuchElementException("Stack underflow");
			}
			Item item = (Item) first.item;
			first = first.next;
			n--;
			return item;
		}

		@Override
		public String toString() {
			StringBuilder s = new StringBuilder();
			for (Item i : this) {
				s.append(" " + i + " ");
			}
			return s.toString();
		}

		@Override
		public Iterator<Item> iterator() {
			return new LinkedIterator<Item>(first);
		}

		private class Node<Item> {
			Item item;
			Node<Item> next;
		}

		private class LinkedIterator<Item> implements Iterator<Item> {
			private Node<Item> current;

			public LinkedIterator(Node<Item> first) {
				this.current = first;
			}

			@Override
			public boolean hasNext() {

				return current != null;
			}

			@Override
			public void remove() {
				throw new UnsupportedOperationException();
			}

			@Override
			public Item next() {
				if (!hasNext()) {
					throw new NoSuchElementException();
				}
				Item item = current.item;
				current = current.next;
				return item;
			}

		}

	}

	static class Node {
		private String item;
		private Node next;
		private Node pre;

		public Node(String item, Node next, Node pre) {
			this.item = item;
			this.next = next;
			this.pre = pre;
		}

		@Override
		public String toString() {
			StringBuilder s = new StringBuilder();
			Node n = this;
			while (n != null) {
				s.append(" " + n.item + " ");
				n = n.next;
			}
			return s.toString();
		}
	}

	private static boolean parenthese(Node n) {
		while (n != null) {
			if (n.item.equals("(") || n.item.equals(")")) {
				return true;
			}
			n = n.next;
		}
		return false;
	}

	private static String cal(String e1, String o, String e2) {
		int r = 0;
		if (o.equals("+")) {
			r = Integer.parseInt(e1) + Integer.parseInt(e2);
		}
		if (o.equals("-")) {
			r = Integer.parseInt(e1) - Integer.parseInt(e2);
		}
		if (o.equals("*")) {
			r = Integer.parseInt(e1) * Integer.parseInt(e2);
		}
		if (o.equals("/")) {
			r = Integer.parseInt(e1) / Integer.parseInt(e2);
		}
		return r + "";
	}

	public static String evaluate(String input) {
		Stack<String> stack = new Stack<String>();
		String[] s = input.split(" ");
		System.out.println(Arrays.toString(s));
		boolean o = false;
		String e;
		Node c, newNode, first;
		c = null;
		first = null;
		for (int i = 0; i < s.length; i++) {
			e = s[i];
			newNode = new Node(e, null, c);
			if (c != null) {
				c.next = newNode;
			}
			c = newNode;
			if (i == 0) {
				first = c;
			}
		}
		System.out.println(first);

		while (parenthese(first)) {
			System.out.println(first);
			c = first;
			Node e1, e2, op;
			String res;
			while (c != null) {
				if (c.item.equals(")")) {
					e2 = c.pre;
					op = e2.pre;
					e1 = op.pre;
					res = cal(e1.item, op.item, e2.item);
					newNode = new Node(res, c.next, e1.pre.pre);
					if (e1.pre.pre != null) {
						e1.pre.pre.next = newNode;
					} else {
						first = newNode;
					}
					if (c.next != null) {
						c.next.pre = newNode;
					}
				}
				c = c.next;
			}
		}
		System.out.println(first);
		c = first;
		Node e1, e2, op;
		String res;
		while (c != null) {
			e=c.item;
			if ( e.equals("*") || e.equals("/")) {
				e1 = c.pre;
				e2 = c.next;
				res = cal(e1.item, c.item, e2.item);
				newNode = new Node(res, c.next.next, c.pre.pre);
				if (c.pre.pre != null) {
					c.pre.pre.next = newNode;
				} else {
					first = newNode;
				}
				if (c.next.next != null) {
					c.next.next.pre = newNode;
				}
			}
			c = c.next;
		}
		c=first;
		while (c != null) {
			e=c.item;
			if ( e.equals("+") || e.equals("-")) {
				e1 = c.pre;
				e2 = c.next;
				res = cal(e1.item, c.item, e2.item);
				newNode = new Node(res, c.next.next, c.pre.pre);
				if (c.pre.pre != null) {
					c.pre.pre.next = newNode;
				} else {
					first = newNode;
				}
				if (c.next.next != null) {
					c.next.next.pre = newNode;
				}
			}
			c = c.next;
		}
		System.out.println(first);
		return "";
	}

	// 1 4 + 3 * 10 5 / +
	public static String evaluatePostfix(String input) {
		String[] s = input.split(" ");
		// System.out.println(Arrays.toString(s));
		Stack<String> stack = new Stack<String>();
		String e;
		int e1, e2, r;
		for (int i = 0; i < s.length; i++) {
			e = s[i];
			if (e.equals("+")) {
				e1 = Integer.parseInt(stack.pop());
				e2 = Integer.parseInt(stack.pop());
				r = e1 + e2;
				stack.push(r + "");
			}
			if (e.equals("-")) {
				e1 = Integer.parseInt(stack.pop());
				e2 = Integer.parseInt(stack.pop());
				r = e1 - e2;
				stack.push(r + "");
			}
			if (e.equals("*")) {
				e1 = Integer.parseInt(stack.pop());
				e2 = Integer.parseInt(stack.pop());
				r = e1 * e2;
				stack.push(r + "");
			}
			if (e.equals("/")) {
				e2 = Integer.parseInt(stack.pop());
				e1 = Integer.parseInt(stack.pop());
				r = e1 / e2;
				stack.push(r + "");
			}

			if (e.matches("\\d+")) {
				stack.push(e);
			}

		}
		return stack.pop();
	}

	// (1 + 4) * 3 + 10 / 5
	public static void main(String[] args) {
		// String r = evaluatePostfix("1 4 + 3 * 10 5 / +");
		// evaluate("( 1 + 4 ) * 3 + 10 / 5");
		
		evaluate("1 + ( ( 2 + 3 ) * ( 5 - 1 ) )");
		String s0="+";
		String s1="+";
		System.out.println(s0.equals(s1));
		System.out.println(s0==s1);
	}

}
